package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //沙袋里最少数目的球
    private boolean check(int m, int[] nums, int cnt) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % m == 0) {
                res += nums[i] / m - 1;
            } else {
                res += nums[i] / m;
            }
        }
        return res <= cnt;
    }

    public int minimumSize(int[] nums, int cnt) {
        int l = 1, r = (int)1e9;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m, nums, cnt)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    //数字 1 的个数
    public int countDigitOne(int n) {
        String s = String.valueOf(n);
        char[] chs = s.toCharArray();
        int len = chs.length, m = 0;
        int[] dp = new int[len];
        for (int i = 1; i < len; i++) {
            dp[i] = 10 * dp[i-1] + (int) Math.pow(10, i-1);
        }
        for (int i = 0; i < len; i++) {
            int t = chs[i] - '0';
            m += dp[len-i-1] * t;
            if (t > 1) m += (int) Math.pow(10, len-i-1);
            if (t == 1) m += ((i+1 < len ? Integer.parseInt(s.substring(i+1, len)) : 0) + 1);
        }
        return m;
    }
}
